package com.chenxys.algorithm.leetcode;

import java.util.*;

/**
 * <p>
 *     <a href="https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/">无重复字符从最长子串</a><br/>
 *      给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。<br/>
 *      例：<br/>
 *          输入: s = "abcabcbb" <br/>
 *          输出: 3 <br/>
 *          解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。<br/>
 * </p>
 *
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.leetcode
 * @date 2024/1/2 14:55
 * @Copyright ©
 */
@SuppressWarnings("all")
public class LeetCode03 {
    /**
     * <p>
     *     获取字符串s中无重复字符的最长长度
     * </p>
     * @param s 字符串
     * @return 无重复字符的最长子串的长度
     */
    public static int lengthOfLongestSubstring(String s) {
        // 边界,s为空
        if (s.length() == 0) return 0;
        // 使用map存入s中的每个字符
        Map<Character, Integer> map = new HashMap<>();
        // 记录最大长度
        int max = 0;
        // 滑动窗口左指针[子串起始位置]
        int left = 0;
        // 对s进行遍历
        for (int i = 0; i < s.length(); i++) {
            /**
             1、首先，判断当前字符是否包含在map中，如果不包含，将该字符添加到map（字符，字符在数组下标）,
             此时没有出现重复的字符，左指针不需要变化。此时不重复子串的长度为：i-left+1，与原来的maxLen比较，取最大值；

             2、如果当前字符 ch 包含在 map中，此时有2类情况：
                 1）当前字符包含在当前有效的子段中，如：abca，当我们遍历到第二个a，当前有效最长子段是 abc，我们又遍历到a，
                 那么此时更新 left 为 map.get(a)+1=1，当前有效子段更新为 bca；
                 2）当前字符不包含在当前最长有效子段中，如：abba，我们先添加a,b进map，此时left=0，我们再添加b，发现map中包含b，
                 而且b包含在最长有效子段中，就是1）的情况，我们更新 left=map.get(b)+1=2，此时子段更新为 b，而且map中仍然包含a，map.get(a)=0；
                 随后，我们遍历到a，发现a包含在map中，且map.get(a)=0，如果我们像1）一样处理，就会发现 left=map.get(a)+1=1，实际上，left此时
                 应该不变，left始终为2，子段变成 ba才对。

             为了处理以上2类情况，我们每次更新left，left=Math.max(left , map.get(ch)+1).
             另外，更新left后，不管原来的 s.charAt(i) 是否在最长子段中，我们都要将 s.charAt(i) 的位置更新为当前的i，
             因此此时新的 s.charAt(i) 已经进入到 当前最长的子段中！
             */
            if (map.containsKey(s.charAt(i))){
                // Math.max 的作用：防止回溯
                left = Math.max(left, map.get(s.charAt(i)) + 1);
            }
            // 字符,索引
            map.put(s.charAt(i), i);
            max = Math.max(max, i - left + 1);
        }
        return max;
    }

    /**
     * <p>
     *     遍历字符串，每次以 i 值记录，不回溯 i 值，用flag记录遍历过程找到的重复的字符的位置。如果遇到重复字符，i-flag 即为子串长度，此时flag重新定位到子串中重复字符的位置，i 继续往后遍历。这里length跟result记录长度。
     *
     * </p>
     * @param s
     * @return
     */
    public static int checkLengthOfLongestSubstring(String s) {
        int index = 0;
        int flag = 0;
        int length = 0;
        int result = 0;
        while (index < s.length()) {
            int pos = s.indexOf(s.charAt(index),flag);
            if (pos < index) {
                if (length > result) {
                    result = length;
                }
                if (result >= s.length() - pos - 1) {
                    return result;
                }
                length = index - pos - 1;
                flag = pos + 1;
            }
            length++;
            index++;
        }
        return length;
    }


    public static String generateRandomString(int maxLen, char end) {
        int len = (int) (Math.random() * (maxLen + 1));
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < len; i++) {
            char val = (char) (Math.random() * (int) (end) + 64);
            if (val < 'A' || (val > 'Z' && val < 'a') || val > 'z') {
                i--;
            } else builder.append(val);

        }
        return builder.toString();
    }
    public static void main(String[] args) {
        int maxLen = 100;
        int testTimes = 10000;
        String s = null;
        System.out.println("Test Begin!");
        for (int i = 0; i < testTimes; i++) {
            s = generateRandomString(100,  'z');
            if (checkLengthOfLongestSubstring(s) != lengthOfLongestSubstring(s)) {
                System.out.println(s);
                System.out.println("Oops");
            }
        }
        System.out.println("Test Finish!");
    }
}
